package Leetcode.DayTest;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: kirito
 * @Date: 2024/5/18 15:33
 * @Description:
 * 找出可整除性得分最大的整数
 * 简单
 * 相关标签
 * 相关企业
 * 提示
 * 给你两个下标从 0 开始的整数数组 nums 和 divisors 。
 *
 * divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。
 *
 * 返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [4,7,9,3,9], divisors = [5,2,3]
 * 输出：3
 * 解释：divisors 中每个元素的可整除性得分为：
 * divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 5 整除。
 * divisors[1] 的可整除性得分为 1 ，因为 nums[0] 能被 2 整除。
 * divisors[2] 的可整除性得分为 3 ，因为 nums[2]、nums[3] 和 nums[4] 都能被 3 整除。
 * 因此，返回 divisors[2] ，它的可整除性得分最大。
 * 示例 2：
 *
 * 输入：nums = [20,14,21,10], divisors = [5,7,5]
 * 输出：5
 * 解释：divisors 中每个元素的可整除性得分为：
 * divisors[0] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被 5 整除。
 * divisors[1] 的可整除性得分为 2 ，因为 nums[1] 和 nums[2] 都能被 7 整除。
 * divisors[2] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被5整除。
 * 由于 divisors[0]、divisors[1] 和 divisors[2] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[2] 。
 * 示例 3：
 *
 * 输入：nums = [12], divisors = [10,16]
 * 输出：10
 * 解释：divisors 中每个元素的可整除性得分为：
 * divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 10 整除。
 * divisors[1] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 16 整除。
 * 由于 divisors[0] 和 divisors[1] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[0] 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length, divisors.length <= 1000
 * 1 <= nums[i], divisors[i] <= 109
 */

public class maxDivScore {
    public static void main(String[] args) {
        int[] a = {4,3,1,6};
        int[][] b = {
                    {0, 2},
                    {2, 3},
                            };
        System.out.println(Arrays.toString(new maxDivScore().isArraySpecial(a, b)));
    }
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        int[] dp = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = dp[i - 1] + (nums[i - 1] % 2 == nums[i] % 2 ? 1 : 0);
        }
        boolean[] ans = new boolean[queries.length];
        //这一步真的妙！灵神！
        //我自己的思想其实是吧数组看成整体了，本质上把相邻两两的看作一起了，拆开看就简单许多了
        for (int i = 0; i < queries.length; i++) {
            int[] q = queries[i];
            ans[i] = dp[q[0]] == dp[q[1]];
        }
        return ans;
    }

    /**
     *如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
     *
     * 你有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助你检查
     * 子数组
     *  nums[fromi..toi] 是不是一个 特殊数组 。
     *
     * 返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。
     *
     * 示例 1：
     *
     * 输入：nums = [3,4,1,2,6], queries = [[0,4]]
     *
     * 输出：[false]
     *
     * 解释：
     *
     * 子数组是 [3,4,1,2,6]。2 和 6 都是偶数。
     *
     * 示例 2：
     *
     * 输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]
     *
     * 输出：[false,true]
     *
     * 解释：
     *
     * 子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。
     * 子数组是 [1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是 true。
     */
    public boolean[] isArraySpecial_violent(int[] nums, int[][] queries) {
        //暴力超时
        int len = queries.length;
        boolean[] ans = new boolean[len];
        int index = 0;

        for (int[] arr : queries) {
            int start = arr[0], end = arr[1];
            ans[index++] = isArraySpecial(nums, start, end);
        }
        return ans;
    }
    //采用二维数组dp存储记录
    public boolean[] isArraySpecial_dp_bug(int[] nums, int[][] queries) {
        //暴力超时
        //dp也超时了。。。。md
        int len = queries.length;
        int nums_len = nums.length;
        boolean[] ans = new boolean[len];
        //DP[j][j]  代表索引i--j是否符合要求  应该是一个上三角的矩形
/*          i	0	1	2	3	4
        j		3	4	1	2	6
        0	3	T	T	T	T	F
        1	4		T	T	T	T
        2	1			T	T	T
        3	2				T	T
        4	6					T*/

        boolean[][] dp = new boolean[nums_len][nums_len];
        for (int i = 0; i < nums_len; i++) {
            dp[i][i] = true;
        }
        for (int i = 0; i < nums_len - 1; i++) {
            for (int j = i + 1; j < nums_len; j++) {
                dp[i][j] = dp[i][j - 1] & (nums[j-1] % 2 != nums[j] % 2);
            }
        }
        int index = 0;
        for (int[] arr : queries) {
            int start = arr[0], end = arr[1];
            ans[index++] = dp[start][end];
        }
        return ans;
    }

    /**
     * 数组范围内是否属于特殊数组
     * @param nums  数组
     * @param start 起始位置
     * @param end   结束位置
     * @return  返回结果
     */
    public boolean isArraySpecial(int[] nums, int start, int end) {
        if (end - start < 1) {
            return true;
        }
        for (int i = start; i < end; i++) {
            if (nums[i] % 2 == nums[i + 1] % 2) {
                return false;
            }
        }
        return true;
    }
    public int maxDivScore(int[] nums, int[] divisors) {
        //存答案0表示值  1表示得分
        int[] ans = new int[2];
        ans[0] = divisors[0];
        for (int num : divisors) {
            int score = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] % num == 0) {
                    score++;
                }
            }
            if (score > ans[1]) {
                ans[0] = num;
                ans[1] = score;
            } else if (score == ans[1]) {
                ans[0] = Math.min(ans[0], num);
            }
        }
        return ans[0];
    }

    public int maxDivScore2(int[] nums, int[] divisors) {
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
            max = Math.max(num, max);//求出nums中的最大值
        }
        int num = 0;
        int res = Integer.MAX_VALUE;
        int pre = -1;
        for (int divisor : divisors) {
            int temp = divisor;
            int k = 0;
            if (pre != divisor) {
                pre = divisor;
                while (temp <= max) {
                    if (map.containsKey(temp)) k += map.get(temp);
                    temp += divisor;
                }
                if (k > num) {
                    num = k;
                    res = divisor;
                } else if (k == num) {
                    res = Math.min(res, divisor);
                }
            }
        }
        return res;
    }
}
